package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func btreeGameWinningMove(root *TreeNode, n, x int) bool {
	lsz, rsz := 0, 0
	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		ls := dfs(node.Left)
		rs := dfs(node.Right)
		if node.Val == x {
			lsz = ls
			rsz = rs
		}
		return 1 + ls + rs
	}
	dfs(root)
	//max(lsz, rsz)*2 > n
	//(n-lsz-rsz-1)*2 > n
	return max(max(lsz, rsz), n-lsz-rsz-1)*2 > n
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

func main() {
	demo := TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 4,
				Left: &TreeNode{
					Val:   8,
					Left:  nil,
					Right: nil,
				},
				Right: &TreeNode{
					Val:   9,
					Left:  nil,
					Right: nil,
				},
			},
			Right: &TreeNode{
				Val: 5,
				Left: &TreeNode{
					Val:   10,
					Left:  nil,
					Right: nil,
				},
				Right: &TreeNode{
					Val:   11,
					Left:  nil,
					Right: nil,
				},
			},
		},
		Right: &TreeNode{
			Val: 3,
			Left: &TreeNode{
				Val: 6,
				Left: &TreeNode{
					Val: 12,
				},
				Right: &TreeNode{
					Val: 13,
				},
			},
			Right: &TreeNode{
				Val: 7,
				//Left: &TreeNode{
				//	Val: 14,
				//},
				//Right: &TreeNode{
				//	Val: 15,
				//},
			},
		},
	}
	fmt.Println(btreeGameWinningMove(&demo, 13, 1))
}
